//
// Created by fh on 2021/6/21.
//

#include "RBTree.h"

/* 前序遍历红黑树:不能修改根节点的属性值 */
void RBTreeDispaly(const RBTreeNode *node) {
    if (!node) {
        return;
    }
    printf("value: %d  color: %s\n",node->value,node->color == 1?"红":"黑");
    RBTreeDispaly(node->leftChild);
    RBTreeDispaly(node->rightChild);
}

/* 创建结点并且根据与data的大小关系直接插入:
 * 这里传进来只需要是结点的指针就行了(传了指针表示结构体的地址，所以能修改的是上一级，即结构体RBTreeNode,也就是结构体的属性能改到
 * 如果是传的RBTreeNode **，那么能修改的就是RBTreeNode *，即结构体的地址，就是能让这个father重新指向，即换个father)
 * 这个需求只需要修改father里面的属性值，也就是它的左孩子或者右孩子就行了，所以传参用RBTreeNode *就够了，这里顺便再复习一下
 * 如果传的是RBTreeNode类型，那么就不是地址，就改不了原来实际参数RBTreeNode的属性值，在函数里如果修改了RBTreeNode的属性值，
 * 那也只是修改了形式参数的属性值，形式参数是实际参数的一份拷贝，所以改不了实际参数 ，如果函数里需要修改到实际参数的都要传地址。这个地方传
 * RBTreeNode **也能修改到实际参数的值，只不过函数内部使用的时候就变复杂了，需要解引用2次才可以访问到RBTreeNode，既然一次就能搞就不整那么麻烦了
 * 而且一不小心还有可能替换掉了父亲 */
RBTreeNode * CreateNodeAndInsertWithFatherAndData(RBTreeNode *father,int data) {
    RBTreeNode *createNode = (RBTreeNode *) malloc(sizeof(RBTreeNode));
    createNode->color = red;
    createNode->value = data;
    createNode->father = father;
    createNode->leftChild = NULL;
    createNode->rightChild = NULL;
    if (data < father->value) {
        father->leftChild = createNode;
    } else {
        father->rightChild = createNode;
    }
    return createNode;
}


/* 祖父右旋
 *            *                         #
 *         #         转变成---->     *        *   父结点是中间那个
 *      *
 * */
void caseOneGrandFatherRightRotate(RBTreeNode *father,RBTreeNode *grandFather,RBTreeNode *greatGrandfather,int grandfatherIsLeft) {
    if (grandFather == NULL || father == NULL) {
        return;
    }
    RBTreeNode *fatherRightChild = father->rightChild;

    grandFather->leftChild = fatherRightChild;
    if (fatherRightChild != NULL) {
        fatherRightChild->father = grandFather;
    }
    grandFather->father = father;
    grandFather->color = red;

    father->rightChild = grandFather;
    father->father = greatGrandfather; // 父结点成为了根节点
    father->color = black;

    if (greatGrandfather != NULL) {
        if (grandfatherIsLeft == 1) {
            /*   #就是father、^就是greatGrandfather
             *
             *            ^                                  ^
             *         *                                 #
             *            #             ------>      *       *
             *               *
             * */
            greatGrandfather->leftChild = father;
        } else {
            /*   #就是father、^就是greatGrandfather
             *
             *      ^                                ^
             *         *                                  #
             *            #             ------>      *        *
             *               *
             * */
            greatGrandfather->rightChild = father;
        }
    }

}

/* 祖父左旋
 *      *                                #
 *         #         转变成---->     *         *   父结点是中间那个
 *            *
 * */
void caseTwoGrandFatherLeftRotate(RBTreeNode *father,RBTreeNode *grandFather,RBTreeNode *greatGrandfather,int grandfatherIsLeft) {
    if (grandFather == NULL || father == NULL) {
        return;
    }
    RBTreeNode *fatherLeftChild = father->leftChild;

    grandFather->rightChild = fatherLeftChild;
    if (fatherLeftChild != NULL) {
        fatherLeftChild->father = grandFather;
    }
    grandFather->father = father;
    grandFather->color = red;

    father->leftChild = grandFather;
    father->father = greatGrandfather;
    father->color = black;

    if (greatGrandfather != NULL) {
        if (grandfatherIsLeft == 1) {
            greatGrandfather->leftChild = father;
        } else {
            greatGrandfather->rightChild = father;
        }
    }
}

/* 红黑树平衡结点操作 */
Status balanceInsert(RBTreeNode *currentNode,RBTreeNode *father) {
    if (currentNode == NULL) {
        // 传参有误，空节点不用处理
        return ERROR;
    }
    if (father == NULL) {
        // 没有父结点说明当前结点就是根结点了，直接设置为黑色
        currentNode->color = black;
        return OK;
    }
    if (father->color == black) {
        // 父结点是黑的,直接插入,什么操作都不用
        return OK;
    } else {
        /*
         * 技巧：把每个可能变化的值都用临时变量保存下来用来getter，不过setter就不要用这个自动变量了，
         * 因为出了函数它就出栈销毁了，除非是用这个自动变量的地址属性，比如 grandFather->father = XXX;
         * 因为这样访问的是greatGrandfather的地址最后会修改掉greatGrandfather的值为XXX，如果直接
         * grandFather = XXX; 就修改不了grandFather的值
         * */

        // 父结点是红色的
        RBTreeNode *grandFather = father->father;
        if (grandFather == NULL) {
            // 没有祖父结点说明父结点就是根结点了，直接设置根节点为黑色
            father->color = black;
            return OK;
        }
        RBTreeNode *uncle = (grandFather->leftChild == father ? grandFather->rightChild : grandFather->leftChild);
        int currentNodeIsLeft = (father->leftChild == currentNode ? 1 : 0);
        int fatherIsLeft = (grandFather->leftChild == father ? 1 : 0);

        if ( (uncle != NULL) && (uncle->color == red) ) {
            // 叔叔是非空红结点
            father->color = black;
            uncle->color = black;
            grandFather->color = red;
            // ---> 继续平衡,后面再弄
            balanceInsert(grandFather,grandFather->father);

        } else if ( (uncle == NULL) || (uncle != NULL && uncle->color == black) ) {
            // 叔叔是非空黑结点
            RBTreeNode *greatGrandfather = grandFather->father;
            int grandfatherIsLeft = (greatGrandfather->leftChild == grandFather ? 1 : 0);

            if (currentNodeIsLeft == 1 && fatherIsLeft == 1) {
                // 当前结点是父结点的左结点
                // 父结点是祖父结点的左结点
                caseOneGrandFatherRightRotate(father,grandFather,greatGrandfather,grandfatherIsLeft);

            } else if (currentNodeIsLeft == 1 && fatherIsLeft == 0) {
                // 当前结点是父结点的左结点
                // 父结点是祖父结点的右结点

                // 第一步: 转成第一种情况再处理(将插入的结点变成了父结点)
                // 这个currentNodeLeftChild其实是空的,因为插入的结点默认是没有子节点的，有的也是nil的空叶子结点
                RBTreeNode *currentNodeRightChild = currentNode->rightChild;

                grandFather->rightChild = currentNode;

                currentNode->father = grandFather;
                currentNode->rightChild = father;

                father->father = currentNode;
                father->leftChild = currentNodeRightChild;
                if (currentNodeRightChild != NULL) {
                    currentNodeRightChild->father = father;
                }
                // 第二步: 处理情况同第四种
                caseTwoGrandFatherLeftRotate(currentNode,grandFather,greatGrandfather,grandfatherIsLeft);

            } else if (currentNodeIsLeft == 0 && fatherIsLeft == 1) {
                // 当前结点是父结点的右结点
                // 父结点是祖父结点的左结点

                // 第一步: 转成第一种情况再处理(将插入的结点变成了父结点)
                // 这个currentNodeLeftChild其实是空的,因为插入的结点默认是没有子节点的，有的也是nil的空叶子结点
                RBTreeNode *currentNodeLeftChild = currentNode->leftChild;

                grandFather->leftChild = currentNode;

                currentNode->father = grandFather;
                currentNode->leftChild = father;

                father->father = currentNode;
                father->rightChild = currentNodeLeftChild;
                if (currentNodeLeftChild != NULL) {
                    currentNodeLeftChild->father = father;
                }
                // 第二步: 处理情况同第一种
                caseOneGrandFatherRightRotate(currentNode,grandFather,greatGrandfather,grandfatherIsLeft);

            } else {
                // 当前结点是父结点的右结点
                // 父结点是祖父结点的右结点
                caseTwoGrandFatherLeftRotate(father,grandFather,greatGrandfather,grandfatherIsLeft);

            }

        }

    }
    return OK;
}


/* 插入结点 */
Status RBTreeInsert(RBTreeNode **root,int data) {
    // 如果根节点为空直接插入
    if (*root == NULL) {
        *root = (RBTreeNode *) malloc(sizeof(RBTreeNode));
        (*root)->color = black;
        (*root)->value = data;
        (*root)->leftChild = NULL;
        (*root)->rightChild = NULL;
        (*root)->father = NULL;
        return OK;
    }
    // 找到插入点的父结点
    RBTreeNode *father = *root;
    while (1) {
        if (data < father->value) {
            if (father->leftChild == NULL) {
                break;
            }
            father = father->leftChild;
        } else if (data > father->value) {
            if (father->rightChild == NULL) {
                break;
            }
            father = father->rightChild;
        } else {
            // 找到相同的值直接返回不用处理了
            return ERROR;
        }
    }
    /*
    // debug
    if (father != NULL) {
        printf("找到的父结点: %d\n",father->value);
    }
    //*/
    // 先插入结点再平衡，father是父结点
    RBTreeNode *createNode = CreateNodeAndInsertWithFatherAndData(father,data);
    // 平衡结点
    return balanceInsert(createNode,father);
}

/* 查找值为data的结点 */
Status RBTreeSelect(RBTreeNode *root,int data,RBTreeNode **findNode) {
    while (root != NULL) {
        if (root->value == data) {
            *findNode = root;
            return OK;
        } else if (root->value > data) {
            root = root->leftChild;
        } else {
            root = root->rightChild;
        }
    }
    if (root == NULL) {
        *findNode = NULL;
        // 没找到
        return ERROR;
    }
}


/* 删除只有一个子节点的情况:此时要删除的结点只能是黑色，并且它的一个子结点只能是红色，不然不符合红黑树的定义
 * 这种情况可能修改动到根节点的指向，所以需要传进来RBTreeNode **root重新指定根节点 */
void onlyOneChildDelete(RBTreeNode *deleteNode,RBTreeNode *deleteNodeChild,RBTreeNode **root) {
    if (deleteNode == NULL) {
        // 空结点还删什么删
        return;
    }
    if (deleteNodeChild == NULL) {
        /* 没有子结点就不是这个函数处理的事情了,这个函数就是处理有一个非空子结点的情况，
         * 你子结点都没有还处理啥,所以也直接返回，说明参数不对
         * */
        return;
    }
    RBTreeNode *father = deleteNode->father;
    if (father == NULL) {
        // 说明要删除的结点是根结点
        // 设置它的子结点为根结点
        deleteNodeChild->color = black;
        deleteNodeChild->father = NULL;
        // 其实外部可能还有指向这个结点的指针，所以需要传进来外部的指针地址root进行修改
        (*root) = deleteNodeChild;
    } else {
        if (father->leftChild == deleteNode) {
            father->leftChild = deleteNodeChild;
            deleteNodeChild->father = father;
            deleteNodeChild->color = black;
        } else if (father->rightChild == deleteNode) {
            father->rightChild = deleteNodeChild;
            deleteNodeChild->father = father;
            deleteNodeChild->color = black;
        }
    }
    free(deleteNode);
    deleteNode = NULL; // 其实外部可能还有指向这个结点的指针，所以需要传进来外部的指针地址root进行修改
}

/* 父亲节点旋转，参数isLeft == 1左旋，否则右旋 */
Status fatherRotate(RBTreeNode *father,RBTreeNode *brother,RBTreeNode *grandfather,int isLeft,RBTreeNode **root) {
    if (father == NULL || brother == NULL) {
        // 这种情况不符合这个函数要处理的情况，直接报错
        return ERROR;
    }
    // 兄弟和父亲颜色互换
    Color tempColor = father->color;
    father->color = brother->color;
    brother->color = tempColor;

    if (isLeft == 1) {
        if (grandfather != NULL) {
            if (grandfather->leftChild == father) {
                grandfather->leftChild = brother;
            } else if (grandfather->rightChild == father) {
                grandfather->rightChild = brother;
            } else {
                // 这棵树有问题
                return ERROR;
            }
        }
        // 需要这个中间变量，不然后面一改左孩子这个就丢失了
        RBTreeNode *leftNephew = brother->leftChild;

        father->father = brother;
        father->rightChild = leftNephew;

        brother->father = grandfather;
        brother->leftChild = father;

        if (leftNephew != NULL) {
            leftNephew->father = father;
        }
        // 如果祖父结点是空的话说明父结点是根节点，此时转化后需要重新指定根节点
        // 需要外部传进来的
        if (grandfather == NULL) {
            *root = brother;
        }

    } else {
        if (grandfather != NULL) {
            if (grandfather->leftChild == father) {
                grandfather->leftChild = brother;
            } else if (grandfather->rightChild == father) {
                grandfather->rightChild = brother;
            } else {
                // 这棵树有问题
                return ERROR;
            }
        }
        // 需要这个中间变量，不然后面一改右孩子这个就丢失了
        RBTreeNode *rightNephew = brother->rightChild;

        father->father = brother;
        father->leftChild = rightNephew;

        brother->father = grandfather;
        brother->rightChild = father;

        if (rightNephew != NULL) {
            rightNephew->father = father;
        }
        // 如果祖父结点是空的话说明父结点是根节点，此时转化后需要重新指定根节点
        // 需要外部传进来的
        if (grandfather == NULL) {
            *root = brother;
        }
    }
}

/* 平衡操作，不用删除，只是调整,此时不用管子结点了，因为子结点已经调整好了: */
Status balanceDelete(RBTreeNode *balanceNode,RBTreeNode **root) {
    // 此时的平衡结点是黑色的,即balanceNode的颜色是黑色
    RBTreeNode *father = balanceNode->father;
    if (father == NULL) {
        // 此时这个结点已经是根节点了，不需要平衡了
        balanceNode->color = black;
        return OK;
    } else {
        // 有父结点
        RBTreeNode *brother = (father->leftChild == balanceNode ? father->rightChild : father->leftChild);
        if (father->leftChild == balanceNode) {
            // 要平衡的结点是左结点
            if (brother != NULL) {
                RBTreeNode *grandfather = father->father;
                if (brother->color == red) {
                    // 兄弟是红的
                    // 先将兄弟变成黑的再统一处理
                    fatherRotate(father,brother,grandfather,1,root);
                    balanceDelete(balanceNode,root);
                } else {
                    // 兄弟是黑的
                    RBTreeNode *leftNephew = brother->leftChild; // 左侄子
                    RBTreeNode *rightNephew = brother->rightChild; // 右侄子
                    if (leftNephew == NULL && rightNephew == NULL) {
                        // 两个侄子都是空的
                        if (father->color == red) {
                            // 父结点是红色的
                            father->color = black;
                            brother->color = red;
                            // 如果是删除操作，将父亲节点P改成黑色，将兄弟节点S改成红色，然后删除结点即可
                        } else {
                            // 父结点是黑色的
                            brother->color = red;
                            // 再以P为起始点，继续根据情况进行平衡操作
                            balanceDelete(father,root);
                        }

                    } else if (leftNephew != NULL && rightNephew == NULL) {
                        // 右侄子是空的
                        // 此时左侄子一定是红色的
                        if (leftNephew->color == black) {
                            // 这不符合红黑树的定义
                            return ERROR;
                        }
                        // 先转化为远侄子的情况
                        father->rightChild = leftNephew;
                        brother->father = leftNephew;
                        brother->leftChild = leftNephew->rightChild;
                        if (leftNephew->rightChild != NULL) {
                            leftNephew->rightChild->father = brother;
                        }
                        leftNephew->father = father;
                        leftNephew->rightChild = brother;
                        // 将侄子和兄弟的颜色互换
                        Color temp = leftNephew->color;
                        leftNephew->color = brother->color;
                        brother->color = temp;
                        // 经过以上左侄子右旋就转化为远侄子的情况了
                        if (brother->color == black) {
                            // 转化过程的颜色有误
                            return ERROR;
                        }
                        fatherRotate(father,leftNephew,grandfather,1,root);
                        brother->color = black;

                    } else if (leftNephew == NULL && rightNephew != NULL) {
                        // 这种情况是远侄子情况
                        // 左侄子是空的
                        // 此时右侄子一定是红色的
                        if (rightNephew->color == black) {
                            // 这不符合红黑树的定义
                            return ERROR;
                        }
                        fatherRotate(father,brother,grandfather,1,root);
                        rightNephew->color = black;

                    } else {
                        // 有两个侄子
                        // 此时两个侄子一定都是红色的，如果都是黑色的话就不符合定义了
                        // 这种情况跟远侄子的处理一样的
                        if (rightNephew->color == black) {
                            // 这不符合红黑树的定义
                            return ERROR;
                        }
                        fatherRotate(father,brother,grandfather,1,root);
                        rightNephew->color = black;
                    }
                }
            } else {
                /* 违背红黑树定义,这种情况不存在: 没有兄弟结点，要删除的结点是黑色，那么不管父结点是红色还是黑色都违背了红黑树的定义
                 * 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑节点的数目称为黑高black-height）
                 * */
                return ERROR;
            }
        } else if (father->rightChild == balanceNode) {
            // 要平衡的结点是右结点
            if (brother != NULL) {
                RBTreeNode *grandfather = father->father;
                if (brother->color == red) {
                    // 兄弟是红的
                    // 先将兄弟变成黑的再统一处理
                    fatherRotate(father,brother,grandfather,0,root);
                    // 如果是删除操作的话还需要后续处理
                    balanceDelete(balanceNode,root);
                } else {
                    // 兄弟是黑的
                    RBTreeNode *leftNephew = brother->leftChild; // 左侄子
                    RBTreeNode *rightNephew = brother->rightChild; // 右侄子
                    if (leftNephew == NULL && rightNephew == NULL) {
                        // 两个侄子都是空的
                        if (father->color == red) {
                            // 父结点是红色的
                            father->color = black;
                            brother->color = red;
                            // 如果是删除操作，将父亲节点P改成黑色，将兄弟节点S改成红色，然后删除结点即可
                        } else {
                            // 父结点是黑色的
                            brother->color = red;
                            // 再以P为起始点，继续根据情况进行平衡操作
                            balanceDelete(father,root);
                        }
                    } else if (leftNephew != NULL && rightNephew == NULL) {
                        // 这种情况是远侄子情况
                        // 右侄子是空的
                        // 此时左侄子一定是红色的
                        if (leftNephew->color == black) {
                            // 这不符合红黑树的定义
                            return ERROR;
                        }
                        fatherRotate(father,brother,grandfather,0,root);
                        leftNephew->color = black;

                    } else if (leftNephew == NULL && rightNephew != NULL) {
                        // 左侄子是空的
                        // 此时右侄子一定是红色的
                        // 先转化为远侄子的情况
                        father->leftChild = rightNephew;
                        brother->father = rightNephew;
                        brother->rightChild = rightNephew->leftChild;
                        if (rightNephew->leftChild != NULL) {
                            rightNephew->leftChild->father = brother;
                        }
                        rightNephew->father = father;
                        rightNephew->leftChild = brother;
                        // 将侄子和兄弟的颜色互换
                        Color temp = rightNephew->color;
                        rightNephew->color = brother->color;
                        brother->color = temp;
                        // 经过以上右侄子左旋就转化为远侄子的情况了
                        if (brother->color == black) {
                            // 转化过程的颜色有误
                            return ERROR;
                        }
                        fatherRotate(father,rightNephew,grandfather,0,root);
                        brother->color = black;

                    } else {
                        // 有两个侄子
                        // 此时两个侄子一定都是红色的，如果都是黑色的话就不符合定义了
                        // 这种情况跟远侄子的处理一样的
                        if (leftNephew->color == black) {
                            // 这不符合红黑树的定义
                            return ERROR;
                        }
                        fatherRotate(father,brother,grandfather,0,root);
                        leftNephew->color = black;
                    }
                }
            } else {
                /* 违背红黑树定义,这种情况不存在: 没有兄弟结点，要删除的结点是黑色，那么不管父结点是红色还是黑色都违背了红黑树的定义
                 * 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑节点的数目称为黑高black-height）
                 * */
                return ERROR;
            }
        } else {
            // 这棵树有问题
            return ERROR;
        }
        return OK;
    }
}

/* 删除核心方法 */
Status RBTreeCoreDelete(RBTreeNode *deleteNode,RBTreeNode **root) {
// https://www.cnblogs.com/qingergege/p/7351659.html
    // 如果删除的结点是红结点，那它一定不存在只有一个子节点的情况(不管这个自己是什么颜色)，否则违背了红黑树的定义
    if (deleteNode->leftChild == NULL && deleteNode->rightChild == NULL) {
        // 没有子结点
        // 删除的结点为红色，直接删除
        if (deleteNode->color == red) {
            // 直接删除
            RBTreeNode *father = deleteNode->father;
            if (father == NULL) {
                // 没有父结点说明这个找到的结点是根节点，但是根结点不可能是红色的，如果发现真有这种红色根节点直接报错了,说明这棵红黑树有问题
                return ERROR;
            }
            if (father->leftChild == deleteNode) {
                father->leftChild = NULL;
            } else if (father->rightChild == deleteNode) {
                father->rightChild = NULL;
            } else {
                // 既不是左结点又不是右结点直接报错，说明这棵红黑树有问题
                return ERROR;
            }
            free(deleteNode);
            deleteNode = NULL;
            return OK;
        } else {
            // 删除的结点为黑色：复杂
            Status status = balanceDelete(deleteNode,root);
            // 删除操作
            if (status == OK) {
                RBTreeNode *father = deleteNode->father;
                if (father == NULL) {
                    // 删除的是根节点
                    free(deleteNode);
                    deleteNode = NULL;
                    *root = NULL;
                } else {
                    if (father->leftChild == deleteNode) {
                        father->leftChild = NULL;
                    } else if (father->rightChild == deleteNode) {
                        father->rightChild = NULL;
                    } else {
                        // 既不是左结点又不是右结点直接报错，说明这棵红黑树有问题
                        return ERROR;
                    }
                    free(deleteNode);
                    deleteNode = NULL;
                }
            }
            return status;
        }

    } else if (deleteNode->leftChild != NULL && deleteNode->rightChild == NULL) {
        // 有一个结点,删除的结点肯定是黑结点,并且它的子节点肯定是红结点,否则违背了红黑树的定义
        // 方法：即用D的孩子（左或右）替换D，并将D孩子的颜色改成黑色即可（因为路径上少了一个黑节点，所已将红节点变成黑节点以保持红黑树的性质）
        onlyOneChildDelete(deleteNode,deleteNode->leftChild,root);
    } else if (deleteNode->leftChild == NULL && deleteNode->rightChild != NULL) {
        // 有一个结点,删除的结点肯定是黑结点,并且它的子节点肯定是红结点,否则违背了红黑树的定义
        // 方法：即用D的孩子（左或右）替换D，并将D孩子的颜色改成黑色即可（因为路径上少了一个黑节点，所已将红节点变成黑节点以保持红黑树的性质）
        onlyOneChildDelete(deleteNode,deleteNode->rightChild,root);
    } else {
        // 有两个结点
        // 要删除既有左子树又有右子树的节点，我们首先要找到该节点的直接后继节点，然后用后继节点替换该节点，最后按1或2中的方法删除后继节点即可
        // 后面转化
        RBTreeNode *replaceNode = deleteNode->rightChild;
        while (replaceNode->leftChild != NULL) {
            replaceNode = replaceNode->leftChild;
        }
        printf("后继结点: value:%d color:%s\n",replaceNode->value,replaceNode->color == black ? "黑" : "红");
        // 替换结点
        deleteNode->value = replaceNode->value;
        // 删除替代结点
        RBTreeCoreDelete(replaceNode,root);
    }
    return OK;
}

/* 删除结点：传进来**root是因为删除的过程中可能会重新指定根结点，所以要传指针的指针，例如假如最后把所有元素都删掉了，那么外部的
 * 实际参数root就需要给他置空了，那么传RBTreeNode **类型才能给外部的RBTreeNode *类型置空，不然就是修改形参的值而已 */
Status RBTreeDelete(RBTreeNode **root,int data) {
    // 先找到该结点
    RBTreeNode *findNode = NULL;
    RBTreeSelect(*root,data,&findNode);
    if (findNode == NULL) {
        printf("没有该节点,无需删除\n");
        return OK;
    }
    // 删除核心方法
    Status status = RBTreeCoreDelete(findNode,root);
    return status;
}


/* 红黑树demo */
void RBTreeDemo() {

    {
        printf("--------------------------- 测试两个指向同一块内存的指针其中一个指针释放掉内存后另一个指针还是能访问到的问题 ------------------------\n");
        // 两个指向同一块内存的指针其中一个指针释放掉内存后另一个指针还是能访问到
        // 所以红黑树删除结点如果涉及到根节点的话需要修改外部实参根节点的指向，不然内部形参虽然释放了结点的内存但是外部还是可以指向并且访问这块内存
        RBTreeNode *testNode = (RBTreeNode *) malloc(sizeof(RBTreeNode));
        testNode->color = black;
        testNode->father = NULL;
        testNode->value = 11;
        testNode->leftChild = NULL;
        testNode->rightChild = NULL;
        printf("testNode----> value:%d color:%s\n",testNode->value,testNode->color == black ? "黑" : "红");

        RBTreeNode *p = testNode;
        printf("p----> value:%d color:%s\n",p->value,p->color == black ? "黑" : "红");
        p->value = 33;
        p->color = red;

        free(p);
        // free之后testNode和p都是迷途指针了
        printf("p----> value:%d color:%s\n",p->value,p->color == black ? "黑" : "红");
        p = NULL;

        printf("testNode----> value:%d color:%s\n",testNode->value,testNode->color == black ? "黑" : "红");
//        return;
    }

    {
        printf("--------------------------- 红黑树插入结点 ------------------------\n");
        RBTreeNode *root = NULL;
        int a[] = {50,100,25,115,20,112,118,2,67};
        int length = sizeof(a) / sizeof(int);
        for (int i = 0; i < length; ++i) {
            Status result = RBTreeInsert(&root,a[i]);
            printf("插入结果: %s ------------------------------------------------ \n",result == OK ? "成功" : "失败");
            RBTreeDispaly(root);
        }

        printf("--------------------------- 红黑树查找结点 ------------------------\n");
        RBTreeNode *findNode = NULL;
        RBTreeSelect(root,112,&findNode);
        if (findNode != NULL) {
            printf("找到结点: value:%d  color:%s\n",findNode->value,findNode->color == 1?"红":"黑");
        } else {
            printf("查无此结点\n");
        }

        printf("--------------------------- 红黑树删除结点 ------------------------\n");
        int b[] = {25,20,2,112,100,67,50,115,118};
        int b_length = sizeof(b) / sizeof(int);
        for (int i = 0; i < b_length; ++i) {
            Status result = RBTreeDelete(&root,b[i]);
            printf("---------------- 删除 %d  ------------------------------------------------ 删除结果: %s \n",b[i],result == OK ? "成功" : "失败");
            RBTreeDispaly(root);
        }


    }
    return;
    {
        printf("--------------------------- 红黑树插入结点 ------------------------\n");
        RBTreeNode *root = NULL;
        int a[] = {50,100};
        int length = sizeof(a) / sizeof(int);
        for (int i = 0; i < length; ++i) {
            Status result = RBTreeInsert(&root,a[i]);
            printf("插入结果: %s ------------------------------------------------ \n",result == OK ? "成功" : "失败");
            RBTreeDispaly(root);
        }

        printf("--------------------------- 红黑树删除结点 ------------------------\n");
        Status result = RBTreeDelete(&root,50);
        printf("删除结果: %s ------------------------------------------------ \n",result == OK ? "成功" : "失败");
        RBTreeDispaly(root);

        printf("--------------------------- 红黑树删除结点 ------------------------\n");
        result = RBTreeDelete(&root,100);
        printf("删除结果: %s ------------------------------------------------ \n",result == OK ? "成功" : "失败");
        RBTreeDispaly(root);

    }

}